1. Field of the Invention
The present invention relates to the design of buffer circuits in integrated circuit design and more particularly to a design methodology for designing a buffer circuit that meets specified timing constraints, without making the circuit larger than required.
2. State of the Art
In logic synthesis, automated logic design using a library of standard cells, it is often necessary to provide a signal produced at a particular circuit node to multiple other circuit nodes. The term "fanout" is to describe the forgoing situation; i.e., a signal is fanned out to several and perhaps a multitude of different circuit nodes. Each of the circuit nodes may represent different capacitive loads and may have associated therewith timing constraints in relation to the signal that must be met. In FIG. 1 for example, the output of a NAND gate 11 is designated as a source signal S and is provided in its true form to a terminal T2 and a terminal T4 of AND gates 17 and 23, respectively, and in its inverted form via inverters 15 and 21 to a terminal T1 and a terminal T3 of an AND gate 13 and an OR gate 19, respectively.
Buffer synthesis is an area of logic synthesis that concerns itself with designing a buffer circuit to fan out a signal to multiple signal nodes, providing the necessary drive to meet the timing constraints of each of the nodes while minimizing the size and power consumption of the buffer circuit.
In more precise terms, the task of buffer synthesis is to synthesize a subnetlist which propagates a signal to a number of destinations, in positive or inverted form as specified for each destination, subject to timing and area constraints. The subnetlist is to be constructed using cells from a specified library of cells. Typically, the cells used will consist just of buffer cells and inverter cells.
The simplest way to build a buffer is to connect the source directly by wires to all destinations requiring a non-inverted signal and to the input of a single inverter cell whose output is connected by wires to all destinations requiring an inverted signal. However, this approach could be unacceptably slow if there are a large number of destinations. In general, one needs to add additional inverter or buffer cells to meet the timing constraints.
The inputs to buffer synthesis are:
1. A list of signal names, including one "source signal" and one or more destination signals or "terminals". Each terminal is identified as either a "positive terminal" or a "negative terminal". The "polarity" of a terminal is its status of being positive or negative. PA1 2. For each terminal, there are specified two times (a "rising required time" and a "falling required time") and a load capacitance. PA1 3. For the source signal, there are specified two times (a "source unloaded rising arrival time" and a "source unloaded falling arrival time"), and two numbers (a "source rising ramp factor" and a "source falling ramp factor"). The ramp factors express the drive strength of the source in units of nanoseconds per picofarad. PA1 4. A list of library cells, together with capacitance and timing parameters for each cell. Commonly this list consists of just buffer cells and inverter cells. For definiteness, the following description assumes that each cell is either a one-input one-output non-inverting buffer cell or a one-input one-output inverter cell, and that the parameters of each cell consists of an input capacitance, an output capacitance, an area, a rising propagation delay, a falling propagation delay, a rising ramp factor, and a falling ramp factor. PA1 1. The rising (falling) arrival time for the source signal equals the rising (falling) source unloaded arrival time plus the product of the rising (falling) source ramp factor and the total capacitance (that is, the sum of all cell input capacitances and terminal load capacitances) driven by the source signal. PA1 2. The rising (falling) arrival time for the output of a buffer cell equals the rising (falling) arrival time of its input plus the rising (falling) propagation delay for the cell, plus the product of the rising (falling) ramp factor for the cell and the total capacitance driven by the cell output. PA1 3. The rising (falling) arrival time for the output of an inverter cell equals the falling (rising) arrival time of its input plus the rising (falling) propagation delay for the cell, plus the product of the rising (falling) ramp factor for the cell and the total capacitance driven by the cell output. PA1 C. Leonard Berman and J. Lawrence Carter. "The Fanout Problem: From Theory to Practice". Advanced Research In VLSI, Proceedings of the Decennial CalTech Conference on VLSI March 1989, ed. Charles L. Seitz, 69-99. PA1 Kanwar Jit Singh and Alberto Sangiovanni-Vincentelli. "A Heuristic Algorithm for the Fanout Problem". 27th ACM/IEEE Design Automation Conference, 1990, 357-360. PA1 Herve J. Touati, Cho W. Noon, Robert K. Brayton, and Albert Wang. "Performance-Oriented Technology Mapping". Advanced Research In VLSI, Proceedings of the Sixth MIT Conference, 1990, ed. William J. Dally, 79-97.
In practice, the list of library cells, input (4), is fixed for the duration of the logic synthesis process, during which time the buffer syntheses process will be performed many times with differing choices for inputs (1)-(3).
The output of the buffer synthesis process is a subnetlist, which serves to propagate the source signal to all the terminals. The source signal is propagated in non-inverted form to each positive terminal and in inverted form to each negative terminal. The subnetlist is composed of cells from the list of library cells and may also utilize directly wired connections from the source to a terminal. In practice, it is desirable for the netlist to have the form of a tree, with the root of the tree being the source signal, the leaves of the tree being the terminals, and with a library cell placed at each internal node of the tree. The source signal and the output pins of the cells are each connected to one or more fanout points, where a fanout point may be either a terminal or the input pin of another cell.
If possible, the subnetlist produced will meet the timing constraints. That is, the arrival times (rising and falling) at each terminal will be no later than the corresponding required times (rising and falling) for that terminal, when delays through the subnetlist are computed by the following rules:
The overall goal is to produce a subnetlist that meets the timing constraints and, subject to meeting these constraints, has the smallest possible area, where area is defined as the sum of the areas of all the cells in the subnetlist.
Wire propagation delays (that is, the time it takes a signal to propagate through the interconnecting wires) are not explicitly considered in this process. In fact, in the usual logic synthesis design flow, individual wire lengths are not specified at the time of logic synthesis, but are determined afterward by routing software. Allowance can be made for expected wire delays by adjustments to this method; for example, by adding some fixed additional capacitance to the capacitance of each fanout point.
The input data for an example of a buffering problem are set forth in Table 1 below:
TABLE 1 ______________________________________ source rising ramp factor = 2.90 source falling ramp factor = 2.20 source unloaded rising arrival time = .30 source unloaded falling arrival time = .30 number of terminals = 4 load rising falling terminal polarity capacitance reg-time reg-time ______________________________________ T1 pos .300 2.0 1.7 T2 pos .300 3.6 3.8 T3 pos .300 4.3 3.7 T4 neg .300 4.8 4.0 ______________________________________ rise library prop rise ramp fall prop fall ramp input output cell delay factor delay factor pin cap pin cap ______________________________________ invert- ers: in01d1 0.33 2.91 .21 1.31 .100 .090 in01d2 0.26 1.51 .17 .67 .200 .100 in01d3 0.22 1.03 .16 .46 .303 .178 buffers: ni01d1 0.64 2.90 .96 1.20 .100 .090 ni01d2 0.72 1.51 1.34 .68 .100 .100 ni01d3 0.86 1.01 1.70 .48 .100 .240 ______________________________________
A possible buffering solution which might be produced is shown in FIG. 2.
In the buffering solution of FIG. 2, the various arrival times are as set forth in Table 2 below
TABLE 2 ______________________________________ source rising = .30 + 2.90*(.300 + .200) = 1.75 falling = .30 + 2.20*(.300 + .200) = 1.40 T1 same arrival times as source T4 rising = 1.40 + 0.26 + 1.51*(.100 + .300 + .303) = 2.75 falling = 1.75 + 0.17 + 0.67*(.100 + .300 + .303) = 2.39 T2 rising = 2.39 + 0.22 + 1.03*(.178 + .300 + .300) = 3.41 falling = 2.75 + 0.16 + 0.46*(.178 + .300 + .300) = 3.24 T3 same arrival times as T2 ______________________________________
It can be seen that the buffering is successful, because all terminal arrival times are less than or equal to the corresponding required times.
Buffer design often requires design engineers to draw upon their previous design experience and accumulated expertise. Attempts to fully automate buffer design, i.e., provide a general-purpose buffer synthesis tool, have been fraught with difficulties in that the number of possible solutions to a buffering problem increases exponentially with the number of terminals to which the signal is to be applied. Proposed solutions to the fanout problem are presented in the following references:
As discussed in the foregoing references, one way to deal with the computational complexity of the fanout problem is to limit choices for the buffer circuit to a few fixed trees, chosen in advance. For each tree tried, the terminals, ordered by required time, may be assigned to the leaves of the tree in some fixed order, and a heuristic approach may be used for choosing cells to place at each internal tree node. Another approach is to use a rule-based system, wherein, starting from some initial non-optimal buffering solution, a set of transformation rules is repeatedly applied. Each application of a rule causes some pattern in the existing buffer to be replaced by some other pattern, according to the rule. Usually, the buffer that exists after applying a rule is more optimal than the previously existing buffer.